package com.mutear.ParallelSearcher.sort;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

import com.mutear.ParallelSearcher.utils.IResult;

public abstract class RatioSort implements ISort {

	@Override
	public List<IResult> sort(List<IResult[]> results) {
		ArrayList<IResult> result = new ArrayList<IResult>();
		ArrayList<Double> distance = new ArrayList<Double>();
		ArrayList<Double> average = new ArrayList<Double>();
		
		// 求平均
		for(int i = 0;i < results.size();i++){
			IResult[] iResult = results.get(i);
			int sum = 0;
			for(int j = 0;j < iResult.length;j++){
				sum += iResult[j].getDistance();
			}
			average.add(((double)sum)/iResult.length);
		}
		
		for(int i = 0;i < results.size();i++){
			IResult[] iResult = results.get(i);
			for(int j = 0;j < iResult.length;j++){
				int index = iResult[j].indexInList(result);
				if(index < 0){
					result.add(iResult[j]);
					distance.add(iResult[j].getDistance()/average.get(i));
				}
				else{
					double w = distance.get(index);
					double w2 = iResult[j].getDistance()/average.get(i);
					distance.set(index, w-((w-(int)w)*(w2-(int)w2)));
					result.set(index, removeSimilar(result.get(index), iResult[j]));
				}
			}
		}

		for(int i = 0; i < result.size(); i++){
			result.get(i).setDistance(distance.get(i));
		}
		
		return sortWithWeight(result);
	}
	
	private ArrayList<IResult> sortWithWeight(ArrayList<IResult> result){
		int size = result.size();
		for(int i = 0;i < size;i++){
			int s = size-i;
			for(int j = s/2-1;j >= 0;j--){
				int max = 0;
				if(2*j+2<s && result.get(2*j+1).getDistance()<result.get(2*j+2).getDistance()){
					max = 1;
				}
				if(max == 0){
					if(result.get(j).getDistance() < result.get(2*j+1).getDistance()){
						Collections.swap(result, j, 2*j+1);
					}
				}
				else{
					if(result.get(j).getDistance() < result.get(2*j+2).getDistance()){
						Collections.swap(result, j, 2*j+2);
					}
				}
			}
			Collections.swap(result, 0, s-1);
		}
		return result;
	}
	
	@Override
	public abstract IResult removeSimilar(IResult arg0, IResult arg1);

}
